/**
给你一个整数数组 coins ，表示不同面额的硬币；
以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。
如果没有任何一种硬币组合能组成总金额，返回 -1 。
输入： coins = [1, 2, 5], amount = 11
输出：3
 */
/**
无限--完全背包
最少的硬币个数--最少物品
dp[i] 金额i的最少元素数
dp[i] =min(dp[i], dp[i-coin[j]]+1)
初始化: 1-每个元素都是最大值 防治覆盖 2: dp[0]=0;
 */
var coinChange = function(coins, amount) {
  const dp = Array(amount+1).fill(Infinity);
  dp[0]=0;
  for(let i=0; i<coins.length;i++){
    for(let j=coins[i]; j<=amount;j++){
      dp[j] = Math.min(dp[j], dp[j-coins[i]]+1)
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
};
const coins = [1, 2, 5], amount = 11;
console.log('零钱兑换',coinChange(coins, amount));
/**
 * review1214✅
 */

